The present invention is directed to lookahead adders in general and, in particular, to a carry generating circuit for such a lookahead adder.
Conventional serial ripple carry adders are slow, because the carry signal produced in each stage must await the generation of a carry signal by the next-lower-order stage. Lookahead adders seek to overcome this disadvantage by improving the way in which carry signals are generated. Such adders include a series of summing stages, each for adding a respective pair of corresponding bits of two multi-bit binary numbers. Each summing stage has a pair of A and B bit inputs and a carry input. There is associated with each summing stage a generate and a propagate circuit. Each propagate circuit associated with a given summing stage generates a propagate signal if one of its A and B inputs is true, and each of the generate circuits produces an output if both of its A and B inputs are true. The generate and propagate circuits associated with successive pairs of stages have their outputs applied to a common group generate circuit, and, similarly, the propagate circuits associated with successive pairs of summing circuits have their outputs applied to a common group propagate circuit. Thus, in a 4-bit adder, the generate and propagate circuits of the most-significant and second-most-significant bits have their outputs applied to a first pair of group generate and group propagate circuits, while the generate and propagate circuits associated with the third-most-significant and least-significant bits have their outputs applied to a second pair of group generate and group propagate circuits. The two pairs of group generate and group propagate circuits, in turn, have their outputs applied to a single pair of group generate and group propagate circuits. The result is a pyramid of hierarchically-arranged generate, propagate, group generate, and group propagate circuits going from the generate and propagate circuits at the lowest level to a single pair of group generate and group propagate circuits at the highest level, the circuits at the highest level being removed from the lowest-level generate and propagate circuits by a number of levels, which is a function of the total number of bits in the numbers to be added. Thus, in a 32-bit adder, for example, the pyramid comprises 32 pairs of generate and propagate circuits, 16 pairs of group generate and group propagate circuits at a first intermediate level, eight pairs of such circuits at a second intermediate level, four pairs at a third intermediate level, and two pairs at a fourth intermediate level, so that the total number of levels of group generate and group propagate circuits is five.
Returning to the discussion of a four-bit lookahead adder, each stage of the adder includes a carry generating circuit whose function is to derive from the outputs of the generate, propagate, group generate, and group propagate circuits, carry signals for successive summing stages above the least-significant bit stage. In a four-bit adder, the inputs to the first, second, and fourth carry generating stages are provided by the outputs of various ones of the generate, propagate, group generate, and group propagate circuits, and these inputs fully reflect the A and B inputs to the adder. The same is not true, however, of the second-most-significant bit stage, which receives its input from the generate and propagate circuits associated with that stage. This follows from the organization of the pyramid network, wherein the generate, propagate, group generate, and group propagate signals associated with lower bit stages are not applied to the generate and propagate circuits associated with the second-most-significant bit stage. The information which reflects the inputs to those lower stages must come from elsewhere: the output of the carry generate circuit of the third-most-significant bit stage. What the foregoing implies is that the carry signal produced by the carry generating circuit of the second-most-significant stage cannot be produced until the carry signal of the next-lower-order stage has been produced. It is clear that this involves undesirable delay, and, in adders having a larger number of stages, the problem is compounded and the delay increased. It is therefore an object of the present invention to provide a carry generator for a lookahead adder which obviates the need to rely on the outputs of the carry generating circuits associated with respective stages of the adder to produce inputs to the carry generating circuits associated with higher-order stages of the adder.
In accordance with the invention, there is provided a carry generator for a lookahead adder wherein a set of generate, propagate, group generate, and group propagate circuits provides to the carry generate circuits associated with respective summing stages of the adder, generate, propagate, group generate, and group propagate signals which fully reflect the states of the inputs to all stages of the adder so as to obviate the need to apply the output of any carry generate circuit to any other carry generate circuit above it in the chain of carry generate circuits. The ability to provide such a complete complement of generate, propagate, group generate, and group propagate signals is achieved by adding to the conventional hierarchical arrangement of generate, propagate, group generate, and group propagate circuits, additional non-hierarchical group generate and group propagate circuits whose inputs are derived from other circuits which are at different levels in the pyramid of generate, propagate, group generate, and group propagate circuits.